package com.cdream.basic.algorithm.leetcode.map;

import java.util.Arrays;
import java.util.TreeMap;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author cdream
 * @date 8/26/21
 */
public class Question881 {
    public static void main(String[] args) {
        System.out.println(new Question881().numRescueBoats(new int[]{3, 2, 2, 1}, 3));
    }

    public int numRescueBoats(int[] people, int limit) {
        TreeMap<Integer, Long> map = Arrays.stream(people).boxed().collect(Collectors.groupingBy(Function.identity(), TreeMap::new,
                Collectors.counting()));
        for (int p : people) {

        }
        int count = 0;
        while (!map.isEmpty()) {
            Integer max = map.lastKey();
            subKey(map, max);
            if (!map.isEmpty()) {
                Integer second = map.floorKey(limit - max);
                if (second != null) {
                    subKey(map, second);
                }
            }
            count++;
        }
        return count;
    }

    private void subKey(TreeMap<Integer, Long> map, Integer second) {
        Long s = map.get(second);
        if (s == 1L) {
            map.remove(second);
        } else {
            map.put(second, s - 1);
        }
    }
}
